/*
 * @Author: szx
 * @Date: 2022-03-18 15:33:16
 * @LastEditTime: 2022-03-18 16:02:50
 * @Description:
 * @FilePath: \leetcode\剑指offer\41\41.cpp
 */
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class MedianFinder {
   public:
    priority_queue<int> small;                            // 大根堆放小的
    priority_queue<int, vector<int>, greater<int> > big;  // 小根堆
    MedianFinder() {}

    void addNum(int num) {
        if (small.empty() || num < small.top()) {
            small.push(num);
        } else {
            big.push(num);
        }
        if (small.size() - big.size() == 2) {
            big.push(small.top());
            small.pop();
        } else if (big.size() - small.size() == 2) {
            small.push(big.top());
            big.pop();
        }
    }

    double findMedian() {
        if (small.size() > big.size()) {
            return small.top();
        } else if (small.size() < big.size()) {
            return big.top();
        } else {
            return double(big.top() + small.top()) / 2 ;
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */